package com.zdp.leetcode;

public class 爬楼梯 {
    public static void main(String[] args) {
        爬楼梯 demo = new 爬楼梯();
        System.out.println(demo.climbStairs(3));
        System.out.println(demo.climbStairs1(3));
    }
    int count = 0;
    //超时了，明天看看动态规划，再来进行优化
    public int climbStairs(int n) {
        f(n,0);
        return count;
    }
    public void f(int n,int step){
        if(step>n){
            return ;
        }else if(step==n){
            count++;
        }else{
            f(n,step+1);
            f(n,step+2);
        }
    }
    //假设 f(n) 是 爬到n级台阶的方案 ===> f(n) = f(n-1)+f(n-2)
    //f(n) 是我们所求的答案
    //n=0 n=1 是不被依赖的 f(0) = 1 f(1) = 1
    /*
    * f(n) = f(n-1) + f(n-2)
    *  ||     ||        ||
    *  \/     \/        \/
    * result= n1    +   n2
    * 当i+1 ===> n-2 ==> n-1 ==>n2=n1
    *       ===> n-1 ==>n ===> n1 = result
    * */
    public int climbStairs1(int n) {
        int result = 1;
        int n1=0;
        int n2=0;
        for(int i=1;i<=n;i++){
            n2 = n1;
            n1 = result;
            result = n1+n2;
        }
        return result;
    }
}
